from typing import List


class TreeNode:
    def __init__(self):
        self.parent = None
        self.children = []
        self.is_lock = False
        self.locker = 0  # 1 < user <= 10^4
        self.lock_children = 0  # 上锁的子结点数量


class LockingTree:

    def __init__(self, parent: List[int]):
        self.node_dict = {i: TreeNode() for i in range(len(parent))}
        for i, p in enumerate(parent):
            if p != -1:
                self.node_dict[i].parent = self.node_dict[p]
                self.node_dict[p].children.append(self.node_dict[i])

    def lock(self, num: int, user: int) -> bool:
        node = self.node_dict[num]

        # 如果当前结点已经上锁
        if node.is_lock:
            return False

        # 给当前结点上锁
        node.is_lock = True
        node.locker = user

        # 将存在子结点上锁的消息上传
        while node.parent:
            node = node.parent
            node.lock_children += 1

        return True

    def unlock(self, num: int, user: int) -> bool:
        node = self.node_dict[num]

        # 当前结点未上锁的情况
        if not node.is_lock:
            return False

        # 不是当前用户上锁的情况
        if node.locker != user:
            return False

        # 给当前结点解锁
        node.is_lock = False
        node.locker = 0

        # 将存在子结点解锁的消息上传
        while node.parent:
            node = node.parent
            node.lock_children -= 1

        return True

    def upgrade(self, num: int, user: int) -> bool:
        node = self.node_dict[num]

        # 当前结点已经上锁
        if node.is_lock:
            return False

        # 当前结点没有上锁的子结点
        if node.lock_children == 0:
            return False

        # 当前结点有上锁的祖先节点
        parent = node.parent
        while parent:
            if parent.is_lock:
                return False
            parent = parent.parent

        # 给所有子孙结点解锁
        lock_children_num = 0  # 上锁的子孙结点数量
        queue = [node]
        while queue:
            child = queue.pop()

            # 给子孙结点结点并记录数量
            if child.is_lock:
                child.is_lock = False
                child.locker = 0
                lock_children_num += 1

            # 将子结点的子结点添加到队列
            queue.extend(child.children)

        # 给当前位置上锁
        node.is_lock = True
        node.locker = user

        # 子孙结点上锁数量变化值
        change_lock_children = 1 - lock_children_num

        # 将子孙结点上锁数量变化的消息上传
        while node.parent:
            node = node.parent
            node.lock_children += change_lock_children

        return True


if __name__ == "__main__":
    obj = LockingTree([-1, 0, 0, 1, 1, 2, 2])
    print(obj.lock(2, 2))  # True
    print(obj.unlock(2, 3))  # False
    print(obj.unlock(2, 2))  # True
    print(obj.lock(4, 5))  # True
    print(obj.upgrade(0, 1))  # True
    print(obj.lock(0, 1))  # False
